#include <stdio.h>
#include <stdlib.h>

// 二叉树节点结构体
typedef struct _Node{
    char data;
    struct _Node *lchild;
    struct _Node *rchild;
}node_t;

// 创建二叉树 
// 我们创建一棵树 方便我们写遍历
// 正常情况下 创建一棵树的过程需要考虑的事情很多
int create_tree(node_t **root){
    if(NULL == root){
        return -1;
    }
    char value = 0;
    value = getchar(); // 在终端输入 要存入该节点的数据
    getchar(); //吃掉垃圾字符 \n
    if('#' == value){ // 递归的出口
        return 0;
    }
    *root = (node_t *)malloc(sizeof(node_t));
    if(NULL == *root){
        return -1;
    }
    (*root)->data = value;
    (*root)->lchild = NULL;
    (*root)->rchild = NULL;
    // 创建左子树
    create_tree(&((*root)->lchild));
    // 创建右子树
    create_tree(&((*root)->rchild));
    return 0;
}

// 前序遍历
int qianxu(node_t *root){
    if(NULL == root){ // 递归的出口
        return -1;
    }
    printf("%c", root->data);
    qianxu(root->lchild);
    qianxu(root->rchild);
    return 0;
}

// 中序遍历
int zhongxu(node_t *root){
    if(NULL == root){ // 递归的出口
        return -1;
    }
    zhongxu(root->lchild);
    printf("%c", root->data);
    zhongxu(root->rchild);
    return 0;
}

// 后序遍历
int houxu(node_t *root){
    if(NULL == root){ // 递归的出口
        return -1;
    }
    houxu(root->lchild);
    houxu(root->rchild);
    printf("%c", root->data);
    return 0;
}

// 销毁树
int destroy_tree(node_t **root){
    if(NULL == root || NULL == *root){
        return -1;
    }
    destroy_tree(&(*root)->lchild);
    destroy_tree(&(*root)->rchild);
    free(*root);
    *root = NULL;
    return 0;
}

int main(int argc, const char *argv[]){
    node_t *root = NULL;
    create_tree(&root);
    printf("root = %p\n", root); // 非NULL

    // 前序遍历
    qianxu(root);
    printf("\n");

    // 中序遍历
    zhongxu(root);
    printf("\n");

    // 后序遍历
    houxu(root);
    printf("\n");

    // 销毁树
    destroy_tree(&root);
    printf("root = %p\n", root); // NULL

    return 0;
}